//
//  SBTNode.hpp
//  SBtNode
//
//  Created by chenyh on 2021/2/8.
//

#ifndef SBTNode_hpp
#define SBTNode_hpp

#include <iostream>
/*2.4.1 二叉查找树的定义
 棵形象的二叉查找树如图 2-15 所示。从图中可以归纳出二叉查找树的定义，它是一 棵二叉树，如果根结点的左子树不空，则左子树中所有的结点值均小于根结点;如果根结 点的右子树不为空，则右子树中所有的结点的值均大于根结点;二叉查找树的每一棵子树 也是一棵二叉查找树。
 从定义看出，二叉查找树的定义也是一个递归定义。二叉查找树的每个结点包括数据 域、指针 lChild、指针 rChild 和指针 parent。它们分别对应数据、左孩子指针、右孩子指 针和父结点指针。
 
 */

/*********************二叉查找树结点定义************************/
template <typename DataType> class SBT;
template <typename DataType>
class SBTNode {
private:
    SBTNode<DataType> *lChild,*rChild,*parent;//左孩子指针、右孩子指 针和父结点指针
    DataType data;
public:
    friend class SBT<DataType>;
    SBTNode()
    {
        lChild = rChild = parent = NULL;
        data = NULL;
    }
    SBTNode(DataType d)
    {
        data = d;
        lChild = rChild = parent = NULL;
    }
    /*********************析构函数*******************/
    ~SBTNode()
    {
        lChild = rChild = parent = NULL;
        delete this;
    }
};

template <typename DataType> class SBT
{
private:
    SBTNode<DataType> *root;
public:
    SBT()
    {
        root = new SBT<DataType>();
    }
    SBT(DataType data)
    {
        root = new SBT<DataType>(data);
    }
    // 2.4.2 二叉查找树的基本操作 二叉查找树主要有排序、查询、插入和删除结点集中操作。
    /**
     1.二叉查找树排序
     从定义就可以看出，中序遍历二叉查找树就能将数据从小到大的顺序输出，因此利用 二叉查找树排序只需要实现它的中序遍历操作，从这个意义上说，二叉查找树又叫做二叉 排序树。
     */
    /****************有序输出***********************/
    void inSort(SBTNode<DataType> *node);
    
    /**
     2.二叉查找树的插入操作
     叉查找树的插入操作对于二叉查找树的建立和更新有着重要作用。根据二叉查找树
     的性质，插入操作需要进行以下步骤。
     (1)如果二叉查找树为空，则插入结点就为根结点。
     (2)如果二叉查找树非空，则将待插入的结点与根结点值进行比较，如果小于根结点
     值就插入到根结点的左子树中，如果大于根结点的值，就插入到根结点的右子树中
     从上面步骤可以看出，结点的插入操作是一个递归的过程。
     */
    /******************插入操作**********************/
    void insert(SBTNode<DataType> *node);
    
    /*3.二叉查找树的删除结点操作
     二叉查找树的结点删除操作比较麻烦，需要考虑以下 3 种情况:
     (1)如结点 x 没有子女结点，则修改其父结点的指针，使其指向 x 的指针为 NULL，
     删除结点 x。
     (2)如结点 x 只有一个孩子结点，则修改其父结点的指针和其孩子结点的 parent 指针，
     建立 x 的父结点与其子结点的直接联系，删除结点 x。
     (3)如果结点 x 左右孩子结点都存在，则用 x 的右子树中最小值或者是左子树中的最
     大值来替代 x。
     */
    /******************删除结点***********************/
    void deleteNode(SBTNode<DataType> *node);
    
    /*4.二叉查找树的查询
     查找包含关键字值 K 的结点是二叉查找树的基本操作，具体的操作是从树的根结点开 始比较 K 和结点关键字值的大小，如果小于结点关键字则查找左子树，如果 K 大于结点关 键字，则继续查找右子树。
     */
    SBTNode<DataType>* search(DataType k);
};

template<typename DataType> void SBT<DataType>:: inSort(SBTNode<DataType> *node)
{
    if (node != NULL) {
        inSort(node->lChild);            //递归遍历左孩子结点
        std::cout<<node->data<<std::endl;//输出结点数据
        inSort(node->rChild);            //递归调用右孩子结点
    }
    
}

template<typename DataType> void SBT<DataType>:: insert(SBTNode<DataType> *node)
{
    SBTNode<DataType> *cur,*temp = NULL; //设置两个中间指针
    int count = 0;
    cur = root;
    while (cur != NULL) {
        temp = cur;
        if (node->data < cur->data) {   // 比较待插入结点与当前结点的值
            cur = cur->lChild;          // 如果小于，则遍历左子树
        }else
        {
            cur = cur->rChild;          // 否则遍历右子树
        }
    }
    node->parent = temp;                //将最后一个有效结点设置为待插入结点的父结点
    if (temp == NULL) {
        root = node; //如果根结点为空，则待插入结点为根结点
        count++;
    }else
    {
        if (node->data < temp->data) {  //比较大小
            temp->lChild = node;        //如果小于，则插入为左孩子
            count++;
        }
        else
        {
            temp->rChild = node;        //否则为右孩子
            count++;
        }
        
    }
}

template<typename DataType> void SBT<DataType>:: deleteNode(SBTNode<DataType> *node)
{
    SBTNode<DataType> *p;               //声明待删除结点的父结点指针
    p = node->parent;
    if (node->lChild == NULL && node->rChild == NULL) {
        delete node;
//        count--;        //二叉查找树结点数目减1
    }
    else if(node->lChild == NULL && node->rChild != NULL)
    {
        if (p==NULL) { //判断结点是否为根结点
            root = node->rChild;
//            count--;
        }else
        {
            node->rChild->parent=p;//如不是跟结点，则右孩子结点的父结点指针指向node的父结点
            if (p->lChild == node) { // 判断待删除结点是父结点的左孩子还是右孩子
                p->lChild = node->rChild;
            }else
                p->rChild = node->rChild;
            delete node;
//            count--;
        }
    }else if(node->lChild != NULL && node->rChild == NULL)
    {
        if (p==NULL) { //判断结点是否为根结点
            root = node->lChild;
//            count--;
        }else
        {
            node->lChild->parent=p;//如不是跟结点，则左孩子结点的父结点指针指向node的父结点
            if (p->lChild == node) { // 判断待删除结点是父结点的左孩子还是右孩子
                p->lChild = node->lChild;
            }else
                p->rChild = node->lChild;
            delete node;
//            count--;
        }
    }else
    {
        //如果结点的左右孩子均存在，用node的右子树中最小的结点替换node
        SBTNode<DataType> *left,*curP;  //left指针指向node的右孩子
        left = node->rChild;
        while (left != NULL) { //遍历node右孩子结点左子树
            curP = left;
            left = left->lChild;
        }
        if (curP->rChild != NULL) {
            if (curP->lChild == curP) {
                curP->parent->lChild = curP->rChild;
            }else {
                curP->parent->rChild = curP->rChild;
            }
        }
        else
        {
            curP->parent->lChild = NULL;//替换结点
        }
        curP->parent = p;
        curP->lChild = node->lChild;
        curP->rChild = node->rChild;
        if (p->lChild == node) {
            p->lChild = curP;
        }else {
            p->rChild = curP;
        }
        delete node;
//        count--;
    }
}

template<typename DataType> SBTNode<DataType> * SBT<DataType>:: search(DataType k)
{
    SBTNode<DataType> *node = root;
    while (node != NULL) {
        if (k < node->data) { //如果k小于结点值，则继续查找左子树
            node = node->lChild;
        }else if (k > node->data)
        {
            node = node->rChild;//如果k大于结点值，则继续查找右子树
        }else
            break;  //如果相等，则推出循环
    }
    return node;    //返回结点指针
    
}
#endif /* SBTNode_hpp */
